package com.fan.dynamic;

import java.util.*;

/**
 * 动态规划
 * 背包问题
 *
 * @author 19252
 * @date 2020/8/2
 */
public class KnapsackProblem {

    public static void main(String[] args) {
        // 物品需要占用的空间
        int[] weight = {1, 4, 3};
        // 物品的价值
        int[] value = new int[]{1500, 3000, 2000};
        // 背包的容量
        int capacity = 4;
        // 物品的个数
        int nums = value.length;

        // 创建动态规划需要的二维数组
        // kValueTable[i][j] 表示在前 i 个 物品中能够装入容量为 j 的 背包中的最大价值
        int[][] kValueTable = new int[nums + 1][capacity + 1];

        // 在动态规划表 kValueTable 中 的第一列和第一行全部置为 -1 这一行和列都不需要进行处理
        for (int i = 0; i < kValueTable.length; i++) {
            kValueTable[i][0] = 0;
        }
        Arrays.fill(kValueTable[0], 0);

        // 存放对应的列的最优装配方案
        LinkedHashSet<Integer>[] optimalSolutionOfCapacity = new LinkedHashSet[4];
        optimalSolutionOfCapacity[0] = new LinkedHashSet<>();
        optimalSolutionOfCapacity[1] = new LinkedHashSet<>();
        optimalSolutionOfCapacity[2] = new LinkedHashSet<>();
        optimalSolutionOfCapacity[3] = new LinkedHashSet<>();

        // 临时变量
        LinkedHashSet<Integer> temp;
        int restCapacity;
        // 从第二行第二列开始处理
        for (int i = 1; i < kValueTable.length; i++) {
            for (int j = 1; j < kValueTable[0].length; j++) {
                // 判断当前的背包容量是否能装入这个物品
                if (weight[i - 1] <= j){
                    // 可以装入
                    // 判断
                    // kValueTable[i - 1][j]是上一个同一列的最大值
                    // value[i - 1] + kValueTable[i - 1][j - weight[i - 1]]是当前的物品的价值和装入后的剩余的容量可以装入的最大价值
                    // kValueTable[i][j] = Math.max(kValueTable[i - 1][j], value[i - 1] + kValueTable[i - 1][j - weight[i - 1]]);

                    // 因为我们需要得到的是物品的装配方案，对上面的方法进行改变
                    if (kValueTable[i - 1][j] < value[i - 1] + kValueTable[i - 1][j - weight[i - 1]]){
                        kValueTable[i][j] = value[i - 1] + kValueTable[i - 1][j - weight[i - 1]];

                        // 先清空该列的原有的最优装配方案
                        optimalSolutionOfCapacity[j - 1].clear();
                        // 因为 optimalSolutionOfCapacity 的下标问题
                        restCapacity = j - weight[i - 1];
                        // 对剩余空间进行判断
                        if (restCapacity > 0){
                            // 取出剩余空间的最优装配方案放入该列的方案
                            temp = optimalSolutionOfCapacity[restCapacity - 1];
                            for (Integer index : temp){
                                optimalSolutionOfCapacity[j - 1].add(index);
                            }
                        }
                        // i 代表第几行即放入的物品种类
                        optimalSolutionOfCapacity[j - 1].add(i);
                    }else {
                        kValueTable[i][j] = kValueTable[i - 1][j];
                    }
                }else {
                    kValueTable[i][j] = kValueTable[i - 1][j];
                }
            }
        }
        for (int[] v : kValueTable){
            System.out.println(Arrays.toString(v));
        }
        // 输出各种空间下的最优装配方案
        Arrays.stream(optimalSolutionOfCapacity).forEach(System.out::println);
    }

    public Map<Integer, Integer> map = new HashMap<>();

    /**
     * 求出在一定容量下的背包中可存放物品的最大值，无限背包
     * @param capacity 背包的当前容量
     * @param weight 各个物品需要占用的背包空间
     * @param value 各个物品的价值
     */
    public void optimalSolution(int capacity, int[] weight, int[] value){
        int max = 0;
        int temp;
        map.put(0, 0);
        if (capacity > 0){
            optimalSolution(capacity - 1, weight, value);
        }
        for (int i = 1; i <= capacity / 2; i++) {
            temp = map.get(capacity - i) + map.get(i);
            if (max < temp){
                max = temp;
            }
        }
        for (int i = 0; i < weight.length; i++) {
            if (capacity == weight[i]){
                temp = value[i];
                if (max < temp){
                    max = temp;
                }
            }
        }
        map.put(capacity, max);
    }
}
